/*
 * @lc app=leetcode.cn id=33 lang=javascript
 *
 * [33] 搜索旋转排序数组
 *
 * https://leetcode-cn.com/problems/search-in-rotated-sorted-array/description/
 *
 * algorithms
 * Medium (36.09%)
 * Likes:    322
 * Dislikes: 0
 * Total Accepted:    36.3K
 * Total Submissions: 100.4K
 * Testcase Example:  '[4,5,6,7,0,1,2]\n0'
 *
 * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 * 
 * ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
 * 
 * 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
 * 
 * 你可以假设数组中不存在重复的元素。
 * 
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * 
 * 示例 1:
 * 
 * 输入: nums = [4,5,6,7,0,1,2], target = 0
 * 输出: 4
 * 
 * 
 * 示例 2:
 * 
 * 输入: nums = [4,5,6,7,0,1,2], target = 3
 * 输出: -1
 * 
 */
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  let l = 0, r = nums.length - 1, mid
  if (nums[l] > nums[r]) {
    while(l < r) {
      mid = Math.floor((l + r) / 2)
      if (nums[mid] < nums[r]) {
        r = mid
      } else {
        l = mid + 1
      }
    }
  }
  let ll = 0, rr = nums.length - 1
  if (l !== 0 && target >= nums[0]) rr = l - 1
  else ll = l

  if (nums[rr] < target) return -1
  if (nums[ll] > target) return -1
  while (ll <= rr) {
    let m = Math.floor((rr + ll) / 2)
    if (nums[m] > target) rr = m - 1
    else if (nums[m] < target) ll = m + 1
    else return m
  }
  return -1
};

// let re = search([3, 1], 3)
// console.log(re)

